This notebook compares doublet results calculated on benchmarking datasets to one another, with the primary goal of addressing these questions:

  1. Do methods tend to predict overlapping or distinct sets of doublets on the same dataset?
  2. Is the consensus doublet call across methods predictive of the true doublet status? Here, the “consensus doublets” are those droplets which all methods identify as doublets.

There are several items to bear in mind when interpreting these results:

Setup

Packages

suppressPackageStartupMessages({
  library(SingleCellExperiment)
  library(ggplot2)
  library(patchwork)
  library(caret)
  library(UpSetR)
})

theme_set(theme_bw())

# define threshold used to call cxds
cxds_threshold <- 0.5

Paths

module_base <- rprojroot::find_root(rprojroot::is_renv_project)
data_dir <- file.path(module_base, "scratch", "benchmark-datasets")
result_dir <- file.path(module_base, "results", "benchmark-results")

Functions

plot_pca_calls <- function(df, 
                           color_column, 
                           pred_column,
                           color_lab) {
  # Plot PCs colored by singlet/doublet, showing doublets on top
  # df is expected to contain columns PC1, PC2, `color_column`, and `pred_column`. These should _not_ be provided as strings
  ggplot(df) + 
    aes(x = PC1, 
        y = PC2, 
        color = {{color_column}}) +
  geom_point(
    size = 0.75, 
    alpha = 0.6
  ) +
  scale_color_manual(name = color_lab, values = c("black", "lightblue")) + 
  geom_point(
    data = dplyr::filter(df, {{color_column}} == "doublet"), 
    color = "black",
    size = 0.75
  ) +
  theme(
    legend.title.position = "top",
    legend.position = "bottom"
  )
}

plot_pca_metrics <- function(df, color_column, metric_colors) {
  # Plot PCs colored by performance metric, showing false calls on top
  # metric_colors is a named vector of colors used for coloring tp/tn/fp/fn
  # df is expected to contain columns PC1, PC2, and `color_column`. This should _not_ be provided as a string.
  ggplot(df) + 
    aes(x = PC1, 
        y = PC2, 
        color = {{color_column}}) +
  geom_point(
    size = 0.75, 
    alpha = 0.6
  ) + 
  geom_point(
    data = dplyr::filter(df, {{color_column}} %in% c("fp", "fn")), 
    size = 0.75
  ) +
  scale_color_manual(name = "Call type", values = metric_colors) +
  theme(legend.position = "bottom")
}

Read and prepare input data

First, we’ll read in and combine doublet results into a list of data frames for each dataset. We’ll also create new columns for each dataset:

# find all dataset names to process:
dataset_names <- list.files(result_dir, pattern = "*_scrublet.tsv") |>
  stringr::str_remove("_scrublet.tsv")
# used in PCA plots
confusion_colors <- c(
  "tp" = "lightblue",
  "tn" = "pink",
  "fp" = "blue",
  "fn" = "firebrick2"
)

# Read in data for analysis
doublet_df_list <- dataset_names |>
  purrr::map(
    \(dataset) {
      
      scdbl_tsv <- file.path(result_dir, glue::glue("{dataset}_scdblfinder.tsv"))
      scrub_tsv <- file.path(result_dir, glue::glue("{dataset}_scrublet.tsv"))
      sce_file <- file.path(data_dir, dataset, glue::glue("{dataset}_sce.rds"))
      
      scdbl_df <- scdbl_tsv |>
        readr::read_tsv(show_col_types = FALSE) |>
        dplyr::select(
          barcodes,
          cxds_score, 
          scdbl_score = score, 
          scdbl_prediction  = class
        ) |>
        # add cxds calls at `cxds_threshold` threshold
        dplyr::mutate(
          cxds_prediction = dplyr::if_else(
            cxds_score >= cxds_threshold,
            "doublet",
            "singlet"
          )
        ) 
      
      scrub_df <- readr::read_tsv(scrub_tsv, show_col_types = FALSE) 

      # grab ground truth and PCA coordinates
      sce <- readr::read_rds(sce_file)
      dataset_df <- scuttle::makePerCellDF(sce, use.dimred = "PCA") |>
        tibble::rownames_to_column(var = "barcodes") |>
        dplyr::select(barcodes,
                      ground_truth = ground_truth_doublets, 
                      PC1 = PCA.1, 
                      PC2 = PCA.2) |> 
        dplyr::left_join(
          scrub_df, 
          by = "barcodes"
        ) |>
        dplyr::left_join(
          scdbl_df, 
          by = "barcodes"
        ) 
      
      # Add a consensus call column
      dataset_df <- dataset_df |>
        dplyr::rowwise() |>
        dplyr::mutate(consensus_call = dplyr::if_else(
          all(
            c(scdbl_prediction, scrublet_prediction, cxds_prediction) == "doublet"
          ),
          "doublet", 
          "singlet"
        )) |>
        dplyr::mutate(
          call_type = dplyr::case_when(
            consensus_call == "doublet" && ground_truth == "doublet" ~ "tp",
            consensus_call == "singlet" && ground_truth == "singlet" ~ "tn",
            consensus_call == "doublet" && ground_truth == "singlet" ~ "fp",
            consensus_call == "singlet" && ground_truth == "doublet" ~ "fn"
          )
        )
      
      return(dataset_df)
    }
  ) |> 
  purrr::set_names(dataset_names)

Upset plots

This section contains upset plots that show overlap across doublet calls from each method, displayed for each dataset.

pull_barcodes <- function(df, pred_var) {
  # Helper function to pull out barcodes for doublet calls
  df$barcodes[df[[pred_var]] == "doublet"]
}

upset_list <- doublet_df_list |>
  purrr::iwalk(
    \(df, dataset) {
      
      doublet_barcodes <- list(
        "scDblFinder" = pull_barcodes(df, "scdbl_prediction"),
        "scrublet"    = pull_barcodes(df, "scrublet_prediction"),
        "cxds"        = pull_barcodes(df, "cxds_prediction")
      )
      
      UpSetR::upset(fromList(doublet_barcodes), order.by = "freq") |> print()
      grid::grid.text( # plot title
        dataset,
        x = 0.65, 
        y = 0.95, 
        gp = grid::gpar(fontsize=16)
      ) 

    }
  )

Evaluating consensus performance

This section visualizes and evaluates the consensus doublet calls across each dataset.

PCA

This section plots the PCA for each dataset, with three color schemes from left to right:

  1. Ground truth doublets are shown in black and singlets in blue
  2. Consensus doublets are shown in black and all remaining droplets in blue
  3. Points are colored based on comparing the consensus call to the ground truth as one of:
  • true positive (tp), true negative (tn), false positive (fp), false negative (fn)
# # Make a legend for the confusion-colored PCA
# legend_plot <- data.frame(
#   x = factor(names(confusion_colors), levels = names(confusion_colors)), y = 1:4
# ) |>
#  ggplot(aes(x = x, y = y, color = x)) + 
#   geom_point(size = 3) + 
#   scale_color_manual(name = "Metric", values = confusion_colors) 
# confusion_legend <- ggpubr::get_legend(legend_plot) |> ggpubr::as_ggplot()

doublet_df_list |>
  purrr::iwalk(
    \(df, dataset) {
      
      # First, ground truth
      p1 <- plot_pca_calls(
        df, 
        color_column = ground_truth, 
        color_lab = "Ground truth"
      )
      
      # Second, consensus call
      p2 <- plot_pca_calls(
        df, 
        color_column = consensus_call, 
        color_lab = "Consensus call"
      )
      
      # Third, call type
      p3 <- plot_pca_metrics(
        df,
        call_type, 
        metric_colors = confusion_colors
      )

      # combine and plot
      plot( p1 + p2 + p3 + plot_annotation(glue::glue("PCA for {dataset}")) + plot_layout(ncol=4, widths = c(1,1,1)) )
    }
  )

Performance metrics

This section calculates a confusion matrix and associated statistics on the consensus calls.

metric_df <- doublet_df_list |>
  purrr::imap( 
    \(df, dataset) {
        print(glue::glue("======================== {dataset} ========================"))
      
        cat("Table of consensus calls:")
        print(table(df$consensus_call))
        
        cat("\n\n")
        
        confusion_result <- caret::confusionMatrix(
          # truth should be first
          table(
            "Truth" = df$ground_truth,
            "Consensus prediction" = df$consensus_call
          ), 
          positive = "doublet"
        ) 
        
        print(confusion_result)
        
        # Extract information we want to present later in a table
        tibble::tibble(
          "Dataset name" = dataset,
          "Kappa" = round(confusion_result$overall["Kappa"], 3), 
          "Balanced accuracy" = round(confusion_result$byClass["Balanced Accuracy"], 3)
        )
    }
  ) |>
  dplyr::bind_rows()
======================== hm-6k ========================
Table of consensus calls:
doublet singlet 
    138    6668 


Confusion Matrix and Statistics

         Consensus prediction
Truth     doublet singlet
  doublet     138      33
  singlet       0    6635
                                          
               Accuracy : 0.9952          
                 95% CI : (0.9932, 0.9967)
    No Information Rate : 0.9797          
    P-Value [Acc > NIR] : < 2.2e-16       
                                          
                  Kappa : 0.8908          
                                          
 Mcnemar's Test P-Value : 2.54e-08        
                                          
            Sensitivity : 1.00000         
            Specificity : 0.99505         
         Pos Pred Value : 0.80702         
         Neg Pred Value : 1.00000         
             Prevalence : 0.02028         
         Detection Rate : 0.02028         
   Detection Prevalence : 0.02512         
      Balanced Accuracy : 0.99753         
                                          
       'Positive' Class : doublet         
                                          
======================== HMEC-orig-MULTI ========================
Table of consensus calls:
doublet singlet 
    641   25785 


Confusion Matrix and Statistics

         Consensus prediction
Truth     doublet singlet
  doublet     506    3062
  singlet     135   22723
                                         
               Accuracy : 0.879          
                 95% CI : (0.875, 0.8829)
    No Information Rate : 0.9757         
    P-Value [Acc > NIR] : 1              
                                         
                  Kappa : 0.2079         
                                         
 Mcnemar's Test P-Value : <2e-16         
                                         
            Sensitivity : 0.78939        
            Specificity : 0.88125        
         Pos Pred Value : 0.14182        
         Neg Pred Value : 0.99409        
             Prevalence : 0.02426        
         Detection Rate : 0.01915        
   Detection Prevalence : 0.13502        
      Balanced Accuracy : 0.83532        
                                         
       'Positive' Class : doublet        
                                         
======================== pbmc-1B-dm ========================
Table of consensus calls:
doublet singlet 
     38    3752 


Confusion Matrix and Statistics

         Consensus prediction
Truth     doublet singlet
  doublet      26     104
  singlet      12    3648
                                          
               Accuracy : 0.9694          
                 95% CI : (0.9634, 0.9746)
    No Information Rate : 0.99            
    P-Value [Acc > NIR] : 1               
                                          
                  Kappa : 0.2986          
                                          
 Mcnemar's Test P-Value : <2e-16          
                                          
            Sensitivity : 0.68421         
            Specificity : 0.97228         
         Pos Pred Value : 0.20000         
         Neg Pred Value : 0.99672         
             Prevalence : 0.01003         
         Detection Rate : 0.00686         
   Detection Prevalence : 0.03430         
      Balanced Accuracy : 0.82825         
                                          
       'Positive' Class : doublet         
                                          
======================== pdx-MULTI ========================
Table of consensus calls:
doublet singlet 
      4   10292 


Confusion Matrix and Statistics

         Consensus prediction
Truth     doublet singlet
  doublet       3    1314
  singlet       1    8978
                                          
               Accuracy : 0.8723          
                 95% CI : (0.8657, 0.8787)
    No Information Rate : 0.9996          
    P-Value [Acc > NIR] : 1               
                                          
                  Kappa : 0.0038          
                                          
 Mcnemar's Test P-Value : <2e-16          
                                          
            Sensitivity : 0.7500000       
            Specificity : 0.8723280       
         Pos Pred Value : 0.0022779       
         Neg Pred Value : 0.9998886       
             Prevalence : 0.0003885       
         Detection Rate : 0.0002914       
   Detection Prevalence : 0.1279138       
      Balanced Accuracy : 0.8111640       
                                          
       'Positive' Class : doublet         
                                          

Conclusions

Overall, methods do not have substantial overlap with each other. They each tend to detect different sets of doublets, leading to fairly small sets of consensus doublets. Further, the consensus doublets called by all three methods have some, but not substantial, overlap with the ground truth.

For three out of four datasets, scDblFinder predicts a much larger number of doublets compared to other methods. For pdx-MULTI, however, cxds predicts a much larger number of droplets.

The table below summarizes performance of the “consensus caller”. Note that, in the benchmarking paper these datasets were originally analyzed in, hm-6k was observed to be one of the “easiest” datasets to classify across methods.
Consistent with that observation, it has the highest kappa value here, although it is still fairly low - though not as low as the other methods, which are very close to 0.

metric_df

Compare only scDblFinder and scrublet

Next, we’ll explore consensus scores for just scDblFinder and scrublet.

Session Info

# record the versions of the packages used in this analysis and other environment information
sessionInfo()
R version 4.4.0 (2024-04-24)
Platform: aarch64-apple-darwin20
Running under: macOS Sonoma 14.5

Matrix products: default
BLAS:   /System/Library/Frameworks/Accelerate.framework/Versions/A/Frameworks/vecLib.framework/Versions/A/libBLAS.dylib 
LAPACK: /Library/Frameworks/R.framework/Versions/4.4-arm64/Resources/lib/libRlapack.dylib;  LAPACK version 3.12.0

locale:
[1] en_US.UTF-8/en_US.UTF-8/en_US.UTF-8/C/en_US.UTF-8/en_US.UTF-8

time zone: America/New_York
tzcode source: internal

attached base packages:
[1] stats4    stats     graphics  grDevices datasets  utils     methods   base     

other attached packages:
 [1] UpSetR_1.4.0                caret_6.0-94                lattice_0.22-6             
 [4] patchwork_1.2.0             ggplot2_3.5.1               SingleCellExperiment_1.26.0
 [7] SummarizedExperiment_1.34.0 Biobase_2.64.0              GenomicRanges_1.56.0       
[10] GenomeInfoDb_1.40.0         IRanges_2.38.0              S4Vectors_0.42.0           
[13] BiocGenerics_0.50.0         MatrixGenerics_1.16.0       matrixStats_1.3.0          

loaded via a namespace (and not attached):
 [1] pROC_1.18.5               gridExtra_2.3             rlang_1.1.3              
 [4] magrittr_2.0.3            e1071_1.7-14              compiler_4.4.0           
 [7] DelayedMatrixStats_1.26.0 vctrs_0.6.5               reshape2_1.4.4           
[10] stringr_1.5.1             pkgconfig_2.0.3           crayon_1.5.2             
[13] XVector_0.44.0            labeling_0.4.3            scuttle_1.14.0           
[16] utf8_1.2.4                prodlim_2023.08.28        tzdb_0.4.0               
[19] UCSC.utils_1.0.0          bit_4.0.5                 purrr_1.0.2              
[22] xfun_0.43                 beachmat_2.20.0           zlibbioc_1.50.0          
[25] jsonlite_1.8.8            recipes_1.0.10            DelayedArray_0.30.1      
[28] BiocParallel_1.38.0       parallel_4.4.0            R6_2.5.1                 
[31] stringi_1.8.4             parallelly_1.37.1         rpart_4.1.23             
[34] lubridate_1.9.3           Rcpp_1.0.12               iterators_1.0.14         
[37] knitr_1.46                future.apply_1.11.2       readr_2.1.5              
[40] Matrix_1.7-0              splines_4.4.0             nnet_7.3-19              
[43] timechange_0.3.0          tidyselect_1.2.1          rstudioapi_0.16.0        
[46] abind_1.4-5               yaml_2.3.8                timeDate_4032.109        
[49] codetools_0.2-20          listenv_0.9.1             tibble_3.2.1             
[52] plyr_1.8.9                withr_3.0.0               future_1.33.2            
[55] survival_3.5-8            proxy_0.4-27              pillar_1.9.0             
[58] BiocManager_1.30.23       renv_1.0.7                foreach_1.5.2            
[61] generics_0.1.3            vroom_1.6.5               rprojroot_2.0.4          
[64] hms_1.1.3                 sparseMatrixStats_1.16.0  munsell_0.5.1            
[67] scales_1.3.0              globals_0.16.3            class_7.3-22             
[70] glue_1.7.0                tools_4.4.0               data.table_1.15.4        
[73] ModelMetrics_1.2.2.2      gower_1.0.1               grid_4.4.0               
[76] ipred_0.9-14              colorspace_2.1-0          nlme_3.1-164             
[79] GenomeInfoDbData_1.2.12   cli_3.6.2                 fansi_1.0.6              
[82] S4Arrays_1.4.0            lava_1.8.0                dplyr_1.1.4              
[85] gtable_0.3.5              digest_0.6.35             SparseArray_1.4.3        
[88] farver_2.1.1              lifecycle_1.0.4           hardhat_1.3.1            
[91] httr_1.4.7                bit64_4.0.5               MASS_7.3-60.2            
LS0tCnRpdGxlOiAiQ29tcGFyaXNvbiBhbW9uZyBkb3VibGV0IHByZWRpY3Rpb25zIG9uIGJlbmNobWFya2luZyBkYXRhc2V0cyIKYXV0aG9yOiBTdGVwaGFuaWUgSi4gU3BpZWxtYW4KZGF0ZTogImByIFN5cy5EYXRlKClgIgpvdXRwdXQ6IAogIGh0bWxfbm90ZWJvb2s6CiAgICB0b2M6IHRydWUKICAgIHRvY19kZXB0aDogNAogICAgY29kZV9mb2xkaW5nOiBoaWRlCi0tLQoKVGhpcyBub3RlYm9vayBjb21wYXJlcyBkb3VibGV0IHJlc3VsdHMgY2FsY3VsYXRlZCBvbiBiZW5jaG1hcmtpbmcgZGF0YXNldHMgdG8gb25lIGFub3RoZXIsIHdpdGggdGhlIHByaW1hcnkgZ29hbCBvZiBhZGRyZXNzaW5nIHRoZXNlIHF1ZXN0aW9uczoKCjEuIERvIG1ldGhvZHMgdGVuZCB0byBwcmVkaWN0IG92ZXJsYXBwaW5nIG9yIGRpc3RpbmN0IHNldHMgb2YgZG91YmxldHMgb24gdGhlIHNhbWUgZGF0YXNldD8KMi4gSXMgdGhlIGNvbnNlbnN1cyBkb3VibGV0IGNhbGwgYWNyb3NzIG1ldGhvZHMgcHJlZGljdGl2ZSBvZiB0aGUgdHJ1ZSBkb3VibGV0IHN0YXR1cz8KSGVyZSwgdGhlICJjb25zZW5zdXMgZG91YmxldHMiIGFyZSB0aG9zZSBkcm9wbGV0cyB3aGljaCBhbGwgbWV0aG9kcyBpZGVudGlmeSBhcyBkb3VibGV0cy4KClRoZXJlIGFyZSBzZXZlcmFsIGl0ZW1zIHRvIGJlYXIgaW4gbWluZCB3aGVuIGludGVycHJldGluZyB0aGVzZSByZXN1bHRzOgoKLSBUaGUgZ3JvdW5kIHRydXRoIGNhbGxzIHRoZW1zZWx2ZXMgdG8gd2hpY2ggd2UgYXJlIGNvbXBhcmluZyBjb25zZW5zdXMgY2FsbHMgbWF5IG5vdCBiZSBlbnRpcmVseSBhY2N1cmF0ZSwgc2luY2UgdGhleSB3ZXJlIGFsc28gY29tcHV0YXRpb25hbGx5IGlkZW50aWZpZWQgZ2VuZXJhbGx5IHdpdGggZGVtdWx0aXBsZXhpbmcgYWxnb3JpdGhtcy4gCi0gYGN4ZHNgLCBhcyB3ZSBhcmUgdXNpbmcgaXQsIGRvZXMgbm90IGhhdmUgYSBzcGVjaWZpYyB0aHJlc2hvbGQgZm9yIGNhbGxpbmcgZHJvcGxldHMuIApCeSBjb250cmFzdCwgYm90aCBgc2NydWJsZXRgIGFuZCBgc2NEYmxGaW5kZXJgIGlkZW50aWZ5IGEgdGhyZXNob2xkIGJhc2VkIG9uIHRoZSBnaXZlbiBkYXRhc2V0IHRoZXkgYXJlIHByb2Nlc3NpbmcuIApUaGlzIG5vdGVib29rIHVzZWQgYSBkb3VibGV0IHRocmVzaG9sZCBvZiBgPj0wLjVgIGZvciBgY3hkc2AsIHdoaWNoIG1heSBub3QgYmUgdW5pdmVyc2FsbHkgc3VpdGFibGUgKHRob3VnaCBjaG9vc2luZyBhIHVuaXZlcnNhbGx5IHN1aXRhYmxlIHRocmVzaG9sZCBpcyBub3QgZWFzeSBlaXRoZXIhKS4KCiMjIFNldHVwCgojIyMgUGFja2FnZXMKCgpgYGB7ciBwYWNrYWdlc30Kc3VwcHJlc3NQYWNrYWdlU3RhcnR1cE1lc3NhZ2VzKHsKICBsaWJyYXJ5KFNpbmdsZUNlbGxFeHBlcmltZW50KQogIGxpYnJhcnkoZ2dwbG90MikKICBsaWJyYXJ5KHBhdGNod29yaykKICBsaWJyYXJ5KGNhcmV0KQogIGxpYnJhcnkoVXBTZXRSKQp9KQoKdGhlbWVfc2V0KHRoZW1lX2J3KCkpCgojIGRlZmluZSB0aHJlc2hvbGQgdXNlZCB0byBjYWxsIGN4ZHMKY3hkc190aHJlc2hvbGQgPC0gMC41CmBgYAoKIyMjIFBhdGhzCgoKYGBge3IgYmFzZSBwYXRoc30KbW9kdWxlX2Jhc2UgPC0gcnByb2pyb290OjpmaW5kX3Jvb3QocnByb2pyb290Ojppc19yZW52X3Byb2plY3QpCmRhdGFfZGlyIDwtIGZpbGUucGF0aChtb2R1bGVfYmFzZSwgInNjcmF0Y2giLCAiYmVuY2htYXJrLWRhdGFzZXRzIikKcmVzdWx0X2RpciA8LSBmaWxlLnBhdGgobW9kdWxlX2Jhc2UsICJyZXN1bHRzIiwgImJlbmNobWFyay1yZXN1bHRzIikKYGBgCgojIyMgRnVuY3Rpb25zCgpgYGB7cn0KcGxvdF9wY2FfY2FsbHMgPC0gZnVuY3Rpb24oZGYsIAogICAgICAgICAgICAgICAgICAgICAgICAgICBjb2xvcl9jb2x1bW4sIAogICAgICAgICAgICAgICAgICAgICAgICAgICBwcmVkX2NvbHVtbiwKICAgICAgICAgICAgICAgICAgICAgICAgICAgY29sb3JfbGFiKSB7CiAgIyBQbG90IFBDcyBjb2xvcmVkIGJ5IHNpbmdsZXQvZG91YmxldCwgc2hvd2luZyBkb3VibGV0cyBvbiB0b3AKICAjIGRmIGlzIGV4cGVjdGVkIHRvIGNvbnRhaW4gY29sdW1ucyBQQzEsIFBDMiwgYGNvbG9yX2NvbHVtbmAsIGFuZCBgcHJlZF9jb2x1bW5gLiBUaGVzZSBzaG91bGQgX25vdF8gYmUgcHJvdmlkZWQgYXMgc3RyaW5ncwogIGdncGxvdChkZikgKyAKICAgIGFlcyh4ID0gUEMxLCAKICAgICAgICB5ID0gUEMyLCAKICAgICAgICBjb2xvciA9IHt7Y29sb3JfY29sdW1ufX0pICsKICBnZW9tX3BvaW50KAogICAgc2l6ZSA9IDAuNzUsIAogICAgYWxwaGEgPSAwLjYKICApICsKICBzY2FsZV9jb2xvcl9tYW51YWwobmFtZSA9IGNvbG9yX2xhYiwgdmFsdWVzID0gYygiYmxhY2siLCAibGlnaHRibHVlIikpICsgCiAgZ2VvbV9wb2ludCgKICAgIGRhdGEgPSBkcGx5cjo6ZmlsdGVyKGRmLCB7e2NvbG9yX2NvbHVtbn19ID09ICJkb3VibGV0IiksIAogICAgY29sb3IgPSAiYmxhY2siLAogICAgc2l6ZSA9IDAuNzUKICApICsKICB0aGVtZSgKICAgIGxlZ2VuZC50aXRsZS5wb3NpdGlvbiA9ICJ0b3AiLAogICAgbGVnZW5kLnBvc2l0aW9uID0gImJvdHRvbSIKICApCn0KCnBsb3RfcGNhX21ldHJpY3MgPC0gZnVuY3Rpb24oZGYsIGNvbG9yX2NvbHVtbiwgbWV0cmljX2NvbG9ycykgewogICMgUGxvdCBQQ3MgY29sb3JlZCBieSBwZXJmb3JtYW5jZSBtZXRyaWMsIHNob3dpbmcgZmFsc2UgY2FsbHMgb24gdG9wCiAgIyBtZXRyaWNfY29sb3JzIGlzIGEgbmFtZWQgdmVjdG9yIG9mIGNvbG9ycyB1c2VkIGZvciBjb2xvcmluZyB0cC90bi9mcC9mbgogICMgZGYgaXMgZXhwZWN0ZWQgdG8gY29udGFpbiBjb2x1bW5zIFBDMSwgUEMyLCBhbmQgYGNvbG9yX2NvbHVtbmAuIFRoaXMgc2hvdWxkIF9ub3RfIGJlIHByb3ZpZGVkIGFzIGEgc3RyaW5nLgogIGdncGxvdChkZikgKyAKICAgIGFlcyh4ID0gUEMxLCAKICAgICAgICB5ID0gUEMyLCAKICAgICAgICBjb2xvciA9IHt7Y29sb3JfY29sdW1ufX0pICsKICBnZW9tX3BvaW50KAogICAgc2l6ZSA9IDAuNzUsIAogICAgYWxwaGEgPSAwLjYKICApICsgCiAgZ2VvbV9wb2ludCgKICAgIGRhdGEgPSBkcGx5cjo6ZmlsdGVyKGRmLCB7e2NvbG9yX2NvbHVtbn19ICVpbiUgYygiZnAiLCAiZm4iKSksIAogICAgc2l6ZSA9IDAuNzUKICApICsKICBzY2FsZV9jb2xvcl9tYW51YWwobmFtZSA9ICJDYWxsIHR5cGUiLCB2YWx1ZXMgPSBtZXRyaWNfY29sb3JzKSArCiAgdGhlbWUobGVnZW5kLnBvc2l0aW9uID0gImJvdHRvbSIpCn0KYGBgCgoKIyMgUmVhZCBhbmQgcHJlcGFyZSBpbnB1dCBkYXRhCgpGaXJzdCwgd2UnbGwgcmVhZCBpbiBhbmQgY29tYmluZSBkb3VibGV0IHJlc3VsdHMgaW50byBhIGxpc3Qgb2YgZGF0YSBmcmFtZXMgZm9yIGVhY2ggZGF0YXNldC4KV2UnbGwgYWxzbyBjcmVhdGUgbmV3IGNvbHVtbnMgZm9yIGVhY2ggZGF0YXNldDoKCi0gYGNvbnNlbnN1c19jYWxsYCwgd2hpY2ggd2lsbCBiZSAiZG91YmxldCIgaWYgX2FsbF8gbWV0aG9kcyBwcmVkaWN0ICJkb3VibGV0LCIgYW5kICJzaW5nbGV0IiBvdGhlcndpc2UKLSBgY2FsbF90eXBlYCwgd2hpY2ggd2lsbCBjbGFzc2lmeSB0aGUgY29uc2Vuc3VzIGNhbGwgYXMgb25lIG9mICJ0cCIsICJ0biIsICJmcCIsIG9yICJmbiIgKHRydWUvZmFsc2UgcG9zaXRpdmUvbmVnYXRpdmUpIAoKYGBge3IgcGF0aHN9CiMgZmluZCBhbGwgZGF0YXNldCBuYW1lcyB0byBwcm9jZXNzOgpkYXRhc2V0X25hbWVzIDwtIGxpc3QuZmlsZXMocmVzdWx0X2RpciwgcGF0dGVybiA9ICIqX3NjcnVibGV0LnRzdiIpIHw+CiAgc3RyaW5ncjo6c3RyX3JlbW92ZSgiX3NjcnVibGV0LnRzdiIpCmBgYAoKYGBge3IgcmVhZF9kYXRhfQojIHVzZWQgaW4gUENBIHBsb3RzCmNvbmZ1c2lvbl9jb2xvcnMgPC0gYygKICAidHAiID0gImxpZ2h0Ymx1ZSIsCiAgInRuIiA9ICJwaW5rIiwKICAiZnAiID0gImJsdWUiLAogICJmbiIgPSAiZmlyZWJyaWNrMiIKKQoKIyBSZWFkIGluIGRhdGEgZm9yIGFuYWx5c2lzCmRvdWJsZXRfZGZfbGlzdCA8LSBkYXRhc2V0X25hbWVzIHw+CiAgcHVycnI6Om1hcCgKICAgIFwoZGF0YXNldCkgewogICAgICAKICAgICAgc2NkYmxfdHN2IDwtIGZpbGUucGF0aChyZXN1bHRfZGlyLCBnbHVlOjpnbHVlKCJ7ZGF0YXNldH1fc2NkYmxmaW5kZXIudHN2IikpCiAgICAgIHNjcnViX3RzdiA8LSBmaWxlLnBhdGgocmVzdWx0X2RpciwgZ2x1ZTo6Z2x1ZSgie2RhdGFzZXR9X3NjcnVibGV0LnRzdiIpKQogICAgICBzY2VfZmlsZSA8LSBmaWxlLnBhdGgoZGF0YV9kaXIsIGRhdGFzZXQsIGdsdWU6OmdsdWUoIntkYXRhc2V0fV9zY2UucmRzIikpCiAgICAgIAogICAgICBzY2RibF9kZiA8LSBzY2RibF90c3YgfD4KICAgICAgICByZWFkcjo6cmVhZF90c3Yoc2hvd19jb2xfdHlwZXMgPSBGQUxTRSkgfD4KICAgICAgICBkcGx5cjo6c2VsZWN0KAogICAgICAgICAgYmFyY29kZXMsCiAgICAgICAgICBjeGRzX3Njb3JlLCAKICAgICAgICAgIHNjZGJsX3Njb3JlID0gc2NvcmUsIAogICAgICAgICAgc2NkYmxfcHJlZGljdGlvbiAgPSBjbGFzcwogICAgICAgICkgfD4KICAgICAgICAjIGFkZCBjeGRzIGNhbGxzIGF0IGBjeGRzX3RocmVzaG9sZGAgdGhyZXNob2xkCiAgICAgICAgZHBseXI6Om11dGF0ZSgKICAgICAgICAgIGN4ZHNfcHJlZGljdGlvbiA9IGRwbHlyOjppZl9lbHNlKAogICAgICAgICAgICBjeGRzX3Njb3JlID49IGN4ZHNfdGhyZXNob2xkLAogICAgICAgICAgICAiZG91YmxldCIsCiAgICAgICAgICAgICJzaW5nbGV0IgogICAgICAgICAgKQogICAgICAgICkgCiAgICAgIAogICAgICBzY3J1Yl9kZiA8LSByZWFkcjo6cmVhZF90c3Yoc2NydWJfdHN2LCBzaG93X2NvbF90eXBlcyA9IEZBTFNFKSAKCiAgICAgICMgZ3JhYiBncm91bmQgdHJ1dGggYW5kIFBDQSBjb29yZGluYXRlcwogICAgICBzY2UgPC0gcmVhZHI6OnJlYWRfcmRzKHNjZV9maWxlKQogICAgICBkYXRhc2V0X2RmIDwtIHNjdXR0bGU6Om1ha2VQZXJDZWxsREYoc2NlLCB1c2UuZGltcmVkID0gIlBDQSIpIHw+CiAgICAgICAgdGliYmxlOjpyb3duYW1lc190b19jb2x1bW4odmFyID0gImJhcmNvZGVzIikgfD4KICAgICAgICBkcGx5cjo6c2VsZWN0KGJhcmNvZGVzLAogICAgICAgICAgICAgICAgICAgICAgZ3JvdW5kX3RydXRoID0gZ3JvdW5kX3RydXRoX2RvdWJsZXRzLCAKICAgICAgICAgICAgICAgICAgICAgIFBDMSA9IFBDQS4xLCAKICAgICAgICAgICAgICAgICAgICAgIFBDMiA9IFBDQS4yKSB8PiAKICAgICAgICBkcGx5cjo6bGVmdF9qb2luKAogICAgICAgICAgc2NydWJfZGYsIAogICAgICAgICAgYnkgPSAiYmFyY29kZXMiCiAgICAgICAgKSB8PgogICAgICAgIGRwbHlyOjpsZWZ0X2pvaW4oCiAgICAgICAgICBzY2RibF9kZiwgCiAgICAgICAgICBieSA9ICJiYXJjb2RlcyIKICAgICAgICApIAogICAgICAKICAgICAgIyBBZGQgYSBjb25zZW5zdXMgY2FsbCBjb2x1bW4KICAgICAgZGF0YXNldF9kZiA8LSBkYXRhc2V0X2RmIHw+CiAgICAgICAgZHBseXI6OnJvd3dpc2UoKSB8PgogICAgICAgIGRwbHlyOjptdXRhdGUoY29uc2Vuc3VzX2NhbGwgPSBkcGx5cjo6aWZfZWxzZSgKICAgICAgICAgIGFsbCgKICAgICAgICAgICAgYyhzY2RibF9wcmVkaWN0aW9uLCBzY3J1YmxldF9wcmVkaWN0aW9uLCBjeGRzX3ByZWRpY3Rpb24pID09ICJkb3VibGV0IgogICAgICAgICAgKSwKICAgICAgICAgICJkb3VibGV0IiwgCiAgICAgICAgICAic2luZ2xldCIKICAgICAgICApKSB8PgogICAgICAgIGRwbHlyOjptdXRhdGUoCiAgICAgICAgICBjYWxsX3R5cGUgPSBkcGx5cjo6Y2FzZV93aGVuKAogICAgICAgICAgICBjb25zZW5zdXNfY2FsbCA9PSAiZG91YmxldCIgJiYgZ3JvdW5kX3RydXRoID09ICJkb3VibGV0IiB+ICJ0cCIsCiAgICAgICAgICAgIGNvbnNlbnN1c19jYWxsID09ICJzaW5nbGV0IiAmJiBncm91bmRfdHJ1dGggPT0gInNpbmdsZXQiIH4gInRuIiwKICAgICAgICAgICAgY29uc2Vuc3VzX2NhbGwgPT0gImRvdWJsZXQiICYmIGdyb3VuZF90cnV0aCA9PSAic2luZ2xldCIgfiAiZnAiLAogICAgICAgICAgICBjb25zZW5zdXNfY2FsbCA9PSAic2luZ2xldCIgJiYgZ3JvdW5kX3RydXRoID09ICJkb3VibGV0IiB+ICJmbiIKICAgICAgICAgICkKICAgICAgICApCiAgICAgIAogICAgICByZXR1cm4oZGF0YXNldF9kZikKICAgIH0KICApIHw+IAogIHB1cnJyOjpzZXRfbmFtZXMoZGF0YXNldF9uYW1lcykKYGBgCgoKCgojIyBVcHNldCBwbG90cwoKVGhpcyBzZWN0aW9uIGNvbnRhaW5zIHVwc2V0IHBsb3RzIHRoYXQgc2hvdyBvdmVybGFwIGFjcm9zcyBkb3VibGV0IGNhbGxzIGZyb20gZWFjaCBtZXRob2QsIGRpc3BsYXllZCBmb3IgZWFjaCBkYXRhc2V0LgoKYGBge3J9CnVwc2V0X2xpc3QgPC0gZG91YmxldF9kZl9saXN0IHw+CiAgcHVycnI6Oml3YWxrKAogICAgXChkZiwgZGF0YXNldCkgewogICAgICAKICAgICAgZG91YmxldF9iYXJjb2RlcyA8LSBsaXN0KAogICAgICAgICJzY0RibEZpbmRlciIgPSBkZiRiYXJjb2Rlc1tkZiRzY2RibF9wcmVkaWN0aW9uID09ICJkb3VibGV0Il0sCiAgICAgICAgInNjcnVibGV0IiAgICA9IGRmJGJhcmNvZGVzW2RmJHNjcnVibGV0X3ByZWRpY3Rpb24gPT0gImRvdWJsZXQiXSwKICAgICAgICAiY3hkcyIgICAgICAgID0gZGYkYmFyY29kZXNbZGYkY3hkc19wcmVkaWN0aW9uID09ICJkb3VibGV0Il0KICAgICAgKQogICAgICAKICAgICAgVXBTZXRSOjp1cHNldChmcm9tTGlzdChkb3VibGV0X2JhcmNvZGVzKSwgb3JkZXIuYnkgPSAiZnJlcSIpIHw+IHByaW50KCkKICAgICAgZ3JpZDo6Z3JpZC50ZXh0KCAjIHBsb3QgdGl0bGUKICAgICAgICBkYXRhc2V0LAogICAgICAgIHggPSAwLjY1LCAKICAgICAgICB5ID0gMC45NSwgCiAgICAgICAgZ3AgPSBncmlkOjpncGFyKGZvbnRzaXplPTE2KQogICAgICApIAoKICAgIH0KICApCgpgYGAKCgoKIyMgRXZhbHVhdGluZyBjb25zZW5zdXMgcGVyZm9ybWFuY2UKClRoaXMgc2VjdGlvbiB2aXN1YWxpemVzIGFuZCBldmFsdWF0ZXMgdGhlIGNvbnNlbnN1cyBkb3VibGV0IGNhbGxzIGFjcm9zcyBlYWNoIGRhdGFzZXQuCgoKCiMjIyBQQ0EKClRoaXMgc2VjdGlvbiBwbG90cyB0aGUgUENBIGZvciBlYWNoIGRhdGFzZXQsIHdpdGggdGhyZWUgY29sb3Igc2NoZW1lcyBmcm9tIGxlZnQgdG8gcmlnaHQ6CgoxLiBHcm91bmQgdHJ1dGggZG91YmxldHMgYXJlIHNob3duIGluIGJsYWNrIGFuZCBzaW5nbGV0cyBpbiBibHVlCjIuIENvbnNlbnN1cyBkb3VibGV0cyBhcmUgc2hvd24gaW4gYmxhY2sgYW5kIGFsbCByZW1haW5pbmcgZHJvcGxldHMgaW4gYmx1ZQozLiBQb2ludHMgYXJlIGNvbG9yZWQgYmFzZWQgb24gY29tcGFyaW5nIHRoZSBjb25zZW5zdXMgY2FsbCB0byB0aGUgZ3JvdW5kIHRydXRoIGFzIG9uZSBvZjoKICAtIHRydWUgcG9zaXRpdmUgKGB0cGApLCB0cnVlIG5lZ2F0aXZlIChgdG5gKSwgZmFsc2UgcG9zaXRpdmUgKGBmcGApLCBmYWxzZSBuZWdhdGl2ZSAoYGZuYCkKCgpgYGB7ciwgZmlnLndpZHRoID0gMTIsIGZpZy5oZWlnaHQgPSA2fQpkb3VibGV0X2RmX2xpc3QgfD4KICBwdXJycjo6aXdhbGsoCiAgICBcKGRmLCBkYXRhc2V0KSB7CiAgICAgIAogICAgICAjIEZpcnN0LCBncm91bmQgdHJ1dGgKICAgICAgcDEgPC0gcGxvdF9wY2FfY2FsbHMoCiAgICAgICAgZGYsIAogICAgICAgIGNvbG9yX2NvbHVtbiA9IGdyb3VuZF90cnV0aCwgCiAgICAgICAgY29sb3JfbGFiID0gIkdyb3VuZCB0cnV0aCIKICAgICAgKQogICAgICAKICAgICAgIyBTZWNvbmQsIGNvbnNlbnN1cyBjYWxsCiAgICAgIHAyIDwtIHBsb3RfcGNhX2NhbGxzKAogICAgICAgIGRmLCAKICAgICAgICBjb2xvcl9jb2x1bW4gPSBjb25zZW5zdXNfY2FsbCwgCiAgICAgICAgY29sb3JfbGFiID0gIkNvbnNlbnN1cyBjYWxsIgogICAgICApCiAgICAgIAogICAgICAjIFRoaXJkLCBjYWxsIHR5cGUKICAgICAgcDMgPC0gcGxvdF9wY2FfbWV0cmljcygKICAgICAgICBkZiwKICAgICAgICBjYWxsX3R5cGUsIAogICAgICAgIG1ldHJpY19jb2xvcnMgPSBjb25mdXNpb25fY29sb3JzCiAgICAgICkKCiAgICAgICMgY29tYmluZSBhbmQgcGxvdAogICAgICBwbG90KCBwMSArIHAyICsgcDMgKyBwbG90X2Fubm90YXRpb24oZ2x1ZTo6Z2x1ZSgiUENBIGZvciB7ZGF0YXNldH0iKSkgKyBwbG90X2xheW91dChuY29sPTQsIHdpZHRocyA9IGMoMSwxLDEpKSApCiAgICB9CiAgKQpgYGAKCgojIyMgUGVyZm9ybWFuY2UgbWV0cmljcyAKClRoaXMgc2VjdGlvbiBjYWxjdWxhdGVzIGEgY29uZnVzaW9uIG1hdHJpeCBhbmQgYXNzb2NpYXRlZCBzdGF0aXN0aWNzIG9uIHRoZSBjb25zZW5zdXMgY2FsbHMuIAoKYGBge3J9Cm1ldHJpY19kZiA8LSBkb3VibGV0X2RmX2xpc3QgfD4KICBwdXJycjo6aW1hcCggCiAgICBcKGRmLCBkYXRhc2V0KSB7CiAgICAgICAgcHJpbnQoZ2x1ZTo6Z2x1ZSgiPT09PT09PT09PT09PT09PT09PT09PT09IHtkYXRhc2V0fSA9PT09PT09PT09PT09PT09PT09PT09PT0iKSkKICAgICAgCiAgICAgICAgY2F0KCJUYWJsZSBvZiBjb25zZW5zdXMgY2FsbHM6IikKICAgICAgICBwcmludCh0YWJsZShkZiRjb25zZW5zdXNfY2FsbCkpCiAgICAgICAgCiAgICAgICAgY2F0KCJcblxuIikKICAgICAgICAKICAgICAgICBjb25mdXNpb25fcmVzdWx0IDwtIGNhcmV0Ojpjb25mdXNpb25NYXRyaXgoCiAgICAgICAgICAjIHRydXRoIHNob3VsZCBiZSBmaXJzdAogICAgICAgICAgdGFibGUoCiAgICAgICAgICAgICJUcnV0aCIgPSBkZiRncm91bmRfdHJ1dGgsCiAgICAgICAgICAgICJDb25zZW5zdXMgcHJlZGljdGlvbiIgPSBkZiRjb25zZW5zdXNfY2FsbAogICAgICAgICAgKSwgCiAgICAgICAgICBwb3NpdGl2ZSA9ICJkb3VibGV0IgogICAgICAgICkgCiAgICAgICAgCiAgICAgICAgcHJpbnQoY29uZnVzaW9uX3Jlc3VsdCkKICAgICAgICAKICAgICAgICAjIEV4dHJhY3QgaW5mb3JtYXRpb24gd2Ugd2FudCB0byBwcmVzZW50IGxhdGVyIGluIGEgdGFibGUKICAgICAgICB0aWJibGU6OnRpYmJsZSgKICAgICAgICAgICJEYXRhc2V0IG5hbWUiID0gZGF0YXNldCwKICAgICAgICAgICJLYXBwYSIgPSByb3VuZChjb25mdXNpb25fcmVzdWx0JG92ZXJhbGxbIkthcHBhIl0sIDMpLCAKICAgICAgICAgICJCYWxhbmNlZCBhY2N1cmFjeSIgPSByb3VuZChjb25mdXNpb25fcmVzdWx0JGJ5Q2xhc3NbIkJhbGFuY2VkIEFjY3VyYWN5Il0sIDMpCiAgICAgICAgKQogICAgfQogICkgfD4KICBkcGx5cjo6YmluZF9yb3dzKCkKYGBgCgoKCiMjIENvbmNsdXNpb25zCgpPdmVyYWxsLCBtZXRob2RzIGRvIG5vdCBoYXZlIHN1YnN0YW50aWFsIG92ZXJsYXAgd2l0aCBlYWNoIG90aGVyLiAKVGhleSBlYWNoIHRlbmQgdG8gZGV0ZWN0IGRpZmZlcmVudCBzZXRzIG9mIGRvdWJsZXRzLCBsZWFkaW5nIHRvIGZhaXJseSBzbWFsbCBzZXRzIG9mIGNvbnNlbnN1cyBkb3VibGV0cy4gCkZ1cnRoZXIsIHRoZSBjb25zZW5zdXMgZG91YmxldHMgY2FsbGVkIGJ5IGFsbCB0aHJlZSBtZXRob2RzIGhhdmUgc29tZSwgYnV0IG5vdCBzdWJzdGFudGlhbCwgb3ZlcmxhcCB3aXRoIHRoZSBncm91bmQgdHJ1dGguIAoKRm9yIHRocmVlIG91dCBvZiBmb3VyIGRhdGFzZXRzLCBgc2NEYmxGaW5kZXJgIHByZWRpY3RzIGEgbXVjaCBsYXJnZXIgbnVtYmVyIG9mIGRvdWJsZXRzIGNvbXBhcmVkIHRvIG90aGVyIG1ldGhvZHMuIApGb3IgYHBkeC1NVUxUSWAsIGhvd2V2ZXIsIGBjeGRzYCBwcmVkaWN0cyBhIG11Y2ggbGFyZ2VyIG51bWJlciBvZiBkcm9wbGV0cy4KClRoZSB0YWJsZSBiZWxvdyBzdW1tYXJpemVzIHBlcmZvcm1hbmNlIG9mIHRoZSAiY29uc2Vuc3VzIGNhbGxlciIuIApOb3RlIHRoYXQsIGluIHRoZSBbYmVuY2htYXJraW5nIHBhcGVyIHRoZXNlIGRhdGFzZXRzIHdlcmUgb3JpZ2luYWxseSBhbmFseXplZCBpbl0oaHR0cHM6Ly9kb2kub3JnLzEwLjEwMTYvai5jZWxzLjIwMjAuMTEuMDA4KSwgYGhtLTZrYCB3YXMgb2JzZXJ2ZWQgdG8gYmUgb25lIG9mIHRoZSAiZWFzaWVzdCIgZGF0YXNldHMgdG8gY2xhc3NpZnkgYWNyb3NzIG1ldGhvZHMuICAKQ29uc2lzdGVudCB3aXRoIHRoYXQgb2JzZXJ2YXRpb24sIGl0IGhhcyB0aGUgaGlnaGVzdCBga2FwcGFgIHZhbHVlIGhlcmUsIGFsdGhvdWdoIGl0IGlzIHN0aWxsIGZhaXJseSBsb3cgLSB0aG91Z2ggbm90IGFzIGxvdyBhcyB0aGUgb3RoZXIgbWV0aG9kcywgd2hpY2ggYXJlIHZlcnkgY2xvc2UgdG8gMC4gCgpgYGB7cn0KbWV0cmljX2RmCmBgYAoKCiMjIENvbXBhcmUgb25seSBzY0RibEZpbmRlciBhbmQgc2NydWJsZXQKCk5leHQsIHdlJ2xsIGV4cGxvcmUgY29uc2Vuc3VzIHNjb3JlcyBmb3IgX2p1c3RfIGBzY0RibEZpbmRlcmAgYW5kIGBzY3J1YmxldGAuCgojIyBTZXNzaW9uIEluZm8KCmBgYHtyIHNlc3Npb24gaW5mb30KIyByZWNvcmQgdGhlIHZlcnNpb25zIG9mIHRoZSBwYWNrYWdlcyB1c2VkIGluIHRoaXMgYW5hbHlzaXMgYW5kIG90aGVyIGVudmlyb25tZW50IGluZm9ybWF0aW9uCnNlc3Npb25JbmZvKCkKYGBgCg==